1. Field of the Invention
The present invention relates generally to associative processing and more specifically to an associative processing array structure having a variable word length. Additionally, any of the associative cells in the array may be excluded from a word. The associative processing array of the present invention is particularly advantageously utilized in an LSI (large scale integration) or VLSI (very large scale integration) integrated circuit, in that increased flexibility may be obtained without an increase in the amount of circuitry and pin connections.
Associative processors having the aforementioned variable word length capability and the ability to exclude bits are useful not only in associative processing computers, but also are useful generally in systems requiring a fault tolerant, fast, and flexible computation capability. Such systems include, by way of example, engineering workstations, data base management systems, topological analysis, graphics display, speech recognition, image enhancement, radar applications such as phased arrays, synthetic apertures, echo and wake analysis and tracking, text management systems and telecommunications, including digital filtering applications.
2. Description of the Prior Art
Associative processors may be considered as arrays of single bit processors wherein each single cell only accesses its neighbor cells. Associative processors may be accessed by mutual parallel data streams, the memory thereof is addressable by content and the data structure is based on tags.
While a conventional processor operates on one data item at a time sequentially, an associative processor operates on many data objects simultaneously. For this to be useful, the data objects must be of the same type for any individual instruction so that it is meaningful to apply the same sequential instruction stream to operate simultaneously on these data objects. This class of processor is known as a Single Instruction Multiple Data processor (SIMD).
The associative processor may consist of a rectangular array of single bit computers implemented in LSI, each capable, for example, of having from 2K to 64K bits of memory. These cellular computers obey the same instruction simultaneously, each operating on its own data. The cells can communicate in all four directions with their neighbors and also with external data input and output registers.
The cells in a row of the associative processor array can be dynamically (from one instruction to the next) configured into an arbitrary number of fields of arbitrary defined length (within the constraints of the width of the array). Each field can then operate independently as if it were a separate computer of the given word length, able to perform arithmetic and logical operation. These fields can all obey the same instruction simultaneously, or they may be selectively disabled under program control.
The net effect is that of a set of computers of arbitrarily defined word length, which when they are enabled, obey the saame arithmetic or logic operation simultaneously on different data items. This set of computers can be applied to problems requiring matrix arithmetic, algebra, vector calculations, image (pixal) processing, searching and pattern recognition problems, and speech recognition. They can perform both fixed point and floating point arithmetic to any required accuracy. The throughput of this set of processors is dependent on the size of the array, the length and number of fields and the proportion of the array which is enabled for a particular operation. For example, a 128.times.128 cell array operating on 2048 eight bit numbers simultaneously using a 10 MHz clock is estimated to achieve on the order of 4,000 million additions or logical operations per second and on the order of 1,000 million multiplications per second.
Associative memories, sometimes referred to as Content Addressable Memories, are well known generally, and are organized to function in an associative processor, wherein arithmetic operation may be performed on one or more digital words stored in the memory simultaneously. Such associative processors are described in U.S. Pat. No. 4,068,305. As illustrated by U.S. Pat. No. 4,296,475, such content-addressable memories are word-organized, and efforts have been made to reduce the number of connection pins required for employing the memory. Association between certain bits of an instruction word and previously assigned flags (from status flip-flops, for example) is known such that a data processor executes instructions conditionally by providing masking bits in the instruction word to override one or more association bits. The foregoing is described by U.S. Pat. No. 4,010,452. U.S. Pat. No. 4,044,338 describes an associative memory having separately associable zones. Selective coupling of circuit elements to a data bus wherein each circuit element has an associative address is described by U.S. Pat. No. 4,188,670. U.S. Pat. No. 4,159,538 is illustrative of an LSI associative memory wherein the number of pin connections is reduced by sharing certain package pins by input data, output data and mask information. A serially accessed associative memory is described by U.S. Pat. No. 4,153,943. An Associative Storage Apparatus for Comparing Between Specified Limits is described by U.S. Pat. No. 3,845,465. An Array Processor with processing elements arranged in a rectangular array is described by U.S. Pat. No. 3,979,728. U.S. Pat. No. 3,654,394, Field Effect Transistor Switch, Particularly for Multiplexing, described multiplexing analog signals. U.S. patent application Ser. No. 452,596 filed Dec. 23, 1982 by S. Morton, "Impendance Restoration for Fast Carry Propagation", describes a cellular, dynamically configurable adder.